#pragma once

#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <list>
#include <initializer_list>

using namespace std ;

// list使用了三个类模板来实现功能: Node类、Iterator类、List类
// 为什么要分开定义呢,是因为需要方便访问使用
// 在std里面,迭代器是单独的一个类,并且可以支持多种数据结构通用,且可以在外部使用(优过vector模拟实现的那个方案)
// 这里的链表实现的是双向链表

// 另外一个值得注意的知识点是:
// 在c++中,类内部的typedef的访问权限是决于它在类中的位置和是否显式指定访问说明符的
//
// 如果没有显式标注访问权限的话:
//                在class中: private (因为class的默认访问权限是priveate)
//                在struct中: public (因为struct的访问权限是public)
//
// 但是如果显式标注的话: 就会根据显式控制typedef的访问级别

namespace gojo
{


// Node类

    template<class T>
    struct list_node
    {

        public:

            list_node<T>* _next ;

            list_node<T>* _prev ;

            T _data ;

            list_node (const T& x = T ())
                : _data (x) 
                , _next (nullptr)
                , _prev (nullptr)
            {}      

    } ;


// Iterator类

    // 这里的类模板传了三个模板参数以备用

    template<class T , class Ref , class Ptr>
    struct __list_iterator
    {

        public:

            typedef list_node<T> Node ; // 每个迭代器的类都会选择一个节点

            typedef __list_iterator <T , Ref , Ptr> Self ; // typedef一下,方面声明函数的时候使用

            Node* _node ;

            __list_iterator (Node* node)
                : _node (node)
            {

                // cout << "__list_iterator ()" << endl ;

            }

            Ref operator * ()
            {

                return _node -> _data ;

            } 

            Ptr operator -> ()
            {

                return &_node -> _data ;

            }

            Self& operator ++ () // 前置++
            {

                _node = _node -> _next ;

                return *this ;

            }

            Self operator ++ (int) // 后置++,由于使用要调多一份拷贝,所以不大使用后置++
            {

                Self tmp (*this) ;

                _node = _node -> _next ;

                return tmp ;

            }

            Self& operator -- () // 前置--
            {

                _node = _node -> _prev ;

                return * this ;

            }

            Self operator -- (int) // 后置--
            {

                Self tmp (*this) ;

                _node = _node -> _prev ;

                return tmp ;

            }

            bool operator != (const Self& it) const
            {

                return _node != it._node ;

            }

            bool operator == (const Self& it) const
            {

                return _node == it.node ;

            }

    } ; 


// Reverse_Iterator类

    template<class T , class Ref , class Ptr>
    struct __list_reverse_iterator
    {

        public:

            typedef list_node<T> Node ;

            typedef __list_reverse_iterator<T , Ref , Ptr> Self ;

            Node* _node ;

            __list_reverse_iterator (Node* node)
                : _node (node)
            {}

            Ref operator * ()
            {

                return _node -> _data ;

            } 

            Ptr operator -> ()
            {

                return &_node -> _data ;

            }

            Self& operator ++ () // 前置++
            {

                _node = _node -> _prev ;

                return *this ;

            }

            Self operator ++ (int) // 后置++,由于使用要调多一份拷贝,所以不大使用后置++
            {

                Self tmp (*this) ;

                _node = _node -> _prev ;

                return tmp ;

            }

            Self& operator -- () // 前置--
            {

                _node = _node -> _next ;

                return * this ;

            }

            Self operator -- (int) // 后置--
            {

                Self tmp (*this) ;

                _node = _node -> _next ;

                return tmp ;

            }

            bool operator != (const Self& it) const
            {

                return _node != it._node ;

            }

            bool operator == (const Self& it) const
            {

                return _node == it.node ;

            }

    } ;


// List类

    template<class T>
    class list
    { 

        private:

            typedef list_node<T> Node ;
            
            Node* _head ;

            size_t _size = 0 ; // 设置缺省值,方便在高频读取内容的时候使用


        public:


    // 迭代器

            typedef __list_iterator<T , T& , T*> iterator ;

            typedef __list_iterator<T , const T& , const T*> const_iterator ;

            typedef __list_reverse_iterator<T , T& , T*> reverse_iterator ;

            typedef __list_reverse_iterator<T , const T& , T*> const_reverse_iterator ;

            iterator begin ()
            {

                return iterator (_head -> _next) ;

            }

            iterator end ()
            {

                return iterator (_head) ; // 因为头节点是哨兵节点,所以可以作为尾部(不保存数据)

            }

            const_iterator begin () const
            {

                return const_iterator (_head -> _next) ;

            }

            const_iterator end () const
            {

                return const_iterator (_head) ;

            }

            reverse_iterator rbegin ()
            {

                return reverse_iterator (_head -> _prev) ;

            }

            reverse_iterator rend  ()
            {

                return reverse_iterator (_head) ;

            }

            const_reverse_iterator rbegin () const
            {

                return const_reverse_iterator (_head -> prev) ;

            }

            const_reverse_iterator rend () const
            {

                return const_reverse_iterator (_head) ;

            }


    // 默认函数

            list ()
            {

                empty_init () ; // 通过函数复用来实现初始化

                // cout << "list ()" << endl ;

            }

            list (const list<T>& lt)
            {

                empty_init () ;

                for (const auto& e : lt)
                {

                    push_back (e) ;

                }

            }

            list (initializer_list<T> il)
            {

                empty_init () ;

                for (const auto& e : il)
                {

                    push_back (e) ;

                }

            }

            ~list ()
            {

                clear () ;

                delete _head ;

                _head = nullptr ;

                // cout << "~list ()" << endl ;

            }

    
    // 增

        // 创建节点

            void empty_init ()
            {

                // 创建一个指向自己的双向节点

                _head = new Node ;

                _head -> _next = _head ;

                _head -> _prev = _head ;

            }

            iterator insert (iterator pos , const T& val)
            {

                Node* cur = pos._node ;

                Node* newnode = new Node (val) ;

                Node* prev = cur -> _prev ;

                // prev newcode cur

               prev -> _next = newnode ;

               newnode -> _next = cur ;

               cur -> _prev = newnode ;

               newnode -> _prev = prev ;

               ++_size ;

               return iterator (newnode) ;

            }

            void push_back (const T& x)
            {

                insert (end () , x) ;

            }

            void push_front (const T& x)
            {

                insert (begin () , x) ;

            }

    
    // 删

            iterator erase (iterator pos)
            {

                Node* cur = pos._node ;

                Node* prev = cur -> _prev ;

                Node* next = cur -> _next ;

                prev -> _next = next ;

                next -> _prev = prev ;

                delete cur ;

                --_size ;

                return next ;

            }

            void clear ()
            {

                iterator it = begin () ;

                while (it != end ())
                {

                    it = erase (it) ;

                }
                
            }

            void pop_back ()
            {

                erase (--end ()) ;

            }

            void pop_front ()
            {

                erase (begin ()) ;

            }


    // 改
            
            void swap (list<T>& lt)
            {

                std::swap (_head , lt._head) ;

                std::swap (_size , lt._size) ;

            }

            // lt1 = lt3

            list<T>& operator = (list<T> lt)
            {

                swap (lt) ;

                return *this ;

            }


    // 查

            size_t size () const
            {

                return _size ;

            }

    } ;

}